package com.heima.datastructure.binarysearchtree;

import com.heima.datastructure.binarytree.TreeTraversal;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <strong>二叉搜索树泛型版本</strong><br>
 * <ol>
 *     <li>二叉搜索树的key唯一，不能重复。</li>
 *     <li>二叉搜索树要根据key来排序，所以key必须可以比较</li>
 *     <li>二叉搜索树中任意一个节点作为一棵树的根节点形成的树有：</li>
 *     <ul>
 *         <li>该树的左子树的所有节点的key都要小于根节点的key</li>
 *         <li>该树的右子树的所有节点的key都要大于根节点的key</li>
 *     </ul>
 *     <li>value是用来存值的，可以重复，想象Map集合的key和value，一样的</li>
 *     <li>平衡的二叉搜索树查找数据的时间复杂度为O(log(n))，查找效率非常高</li>
 *     <li>一棵二叉搜索树的最小值（都是按key排序的）就是往左走到底的节点（不能往右走，哪怕有路），最大值（都是按key排序）就是往右走到底的节点（不能往左走，哪怕有路）</li>
 *     <li>二叉搜索树的中序遍历结果就是这棵树的所有节点按key进行升序排序的结果</li>
 *     <li>查找二叉搜索树中某个节点的前驱节点
 *          <ol>
 *              <li>二叉搜索树中某一个节点c，如果有左子树，前驱节点就是c的左子树的最大值</li>
 *              <li>二叉搜索树中某一个节点c，如果没有左子树，前驱节点是其最近的从左而来的祖先节点</li>
 *          </ol>
 *     </li>
 *     <li>查找二叉搜索树中某个节点的后继节点
 *          <ol>
 *               <li>如果有右子树，后继节点就是c的右子树的最小值</li>
 *               <li>如果没有右子树，后继节点是其最近的一个从右而来的祖先节点</li>
 *          </ol>
 *     </li>
 *     <li>删除节点时会遇到的四种情况：
 *         <ol>
 *             <li>删除节点没有左孩子，则将右子树托孤给Parent</li>
 *             <li>删除节点没有右孩子，则将左子树托孤给Parent</li>
 *             <li>删除节点既没有左孩子也没有右孩子，则将null托孤给Parent，前两种情况会涵盖这种</li>
 *             <li>删除节点左右孩子都有，那么删除节点后该位置应该被替换为原删除节点的右子树中的最小值，也就是删除节点的后继节点（左右孩子都有，删除节点的后继必定在右子树中），可以将他的后继节点记为S，再记S的父亲为SP，又有两种情况：
 *                  <ol>
 *                      <li>后继节点就是右子树从根节点往左走到底，如果S是右子树的根节点，（右子树中没有左子树）SP就是被删除节点D，此时D与S相邻，只需要把S托孤给D的Parent，因为D和S是相邻的，只用把D的左子树接到S的左子树即可，S自己会把右子树带上来</li>
 *                      <li>后继节点就是右子树从根节点往左走到底，如果S不是右子树的根节点，（右子树中有左子树）SP不是被删除节点，此时D与S不相邻，此时需要将S的后代（S的后代只可能为null或者右子树，不可能是左子树，S的右子树肯定小于SP）托孤给SP，再将S托孤给D的Parent，这里就是顶替原来D的位置（S是比D大的最小节点，而且S和D不相邻，所以需要把D的左子树、右子树接到S的左子树、右子树）</li>
 *                  </ol>
 *             </li>
 *         </ol>
 *     </li>
 * </ol>
 *
 * @param <K> Key的数据类型，用来比较的，唯一不重复
 * @param <V> value的数据类型，用来存储数据的
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/9 10:20
 */
public class BSTTree<K extends Comparable<K>, V> {
    private BSTNode<K, V> root;

    /**
     * 测试用，不加修饰符，范围是当前包
     *
     * @param root 根节点
     */
    void setRoot(BSTNode<K, V> root) {
        this.root = root;
    }

    /**
     * 获取二叉搜索树的根节点，范围是所有
     *
     * @return 二叉搜索树的根节点
     */
    public BSTNode<K, V> getRoot() {
        return this.root;
    }

    /**
     * 无参构造，root会默认初始化为null
     */
    public BSTTree() {
    }

    /**
     * 有参构造初始化这个树，后续要把传进来的树转化为一个平衡的二叉搜索树
     *
     * @param root 二叉搜索树的根节点
     */
    public BSTTree(BSTNode<K, V> root) {
        this.root = root;
    }

    /**
     * 根据某个key找到对应的值
     *
     * @param key key关键字
     * @return 关键字对应的值
     */
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key不能为空！");
        }
        // return doGet1(root, key);
        return doGet2(key);
    }

    /**
     * 查找最小关键字对应的值
     *
     * @return 关键字对应的值
     */
    public V min() {
        // return doMin1(root);
        return doMin2(root);
    }

    /**
     * 查找最小关键字对应的值
     *
     * @param root 指定节点作为根节点的树
     * @return 关键字对应的值
     */
    private V min(BSTNode<K, V> root) {
        return doMin2(root);
    }

    /**
     * 查找最大关键字对应的值
     *
     * @return 关键字对应的值
     */
    public V max() {
        // return doMax1(root);
        return doMax2(root);
    }

    /**
     * 查找最大关键字对应的值
     *
     * @param root 指定节点作为根节点的树
     * @return 关键字对应的值
     */
    private V max(BSTNode<K, V> root) {
        return doMax2(root);
    }

    /**
     * 存储关键字和对应的值
     *
     * @param key   关键字
     * @param value 值
     */
    public void put(K key, V value) {
        // doPut1(key, value, root, null);
        doPut2(key, value);
    }

    /**
     * 查找关键字的前驱值
     * <ol>
     *     <li>情况一：节点有左子树，那么前驱节点就是左子树的最大值</li>
     *     <li>情况二：节点没有左子树，那么离他最近的从左而来的祖先节点就是前驱节点</li>
     * </ol>
     *
     * @param key 关键字
     * @return 前驱值
     */
    public V predecessor(K key) {
        BSTNode<K, V> curr = root;
        BSTNode<K, V> lastAncestorFromLeft = null; // 用来记录最近的来自左边的一个祖先节点
        while (curr != null) {
            if (key.compareTo(curr.key) < 0) {
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                lastAncestorFromLeft = curr;
                curr = curr.right;
            } else {
                break;
            }
        }
        // key不在该树中，或者root本就是空
        if (curr == null) {
            return null;
        }
        // 如果curr不为空，那么找它的前驱节点
        // 1、有左子树，找左子树的最大值
        if (curr.left != null) {
            return max(curr.left);
        }
        // 2、没有左子树，右子树的节点可定都比它大，只能在祖先节点里面找，找到最近的一个从左而来的祖先节点，就是前驱节点
        if (lastAncestorFromLeft == null) { // 一直在往左走
            return null;
        }
        return lastAncestorFromLeft.value;
    }

    /**
     * 查找关键字的后继值
     * <ol>
     *     <li>情况一：节点有右子树，那么后驱节点就是右子树的最小值</li>
     *     <li>情况二：节点没有右子树，那么后驱节点就是最近的从右而来的祖先节点</li>
     * </ol>
     *
     * @param key 关键字
     * @return 后继值
     */
    public V successor(K key) {
        BSTNode<K, V> curr = root;
        BSTNode<K, V> lastAncestorFromRight = null;
        while (curr != null) {
            if (key.compareTo(curr.key) < 0) {
                lastAncestorFromRight = curr;
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                curr = curr.right;
            } else {
                break;
            }
        }
        // key没找到，或者root本就是空
        if (curr == null) {
            return null;
        }
        // key找到了
        // 1、如果该节点有右子树，则返回右子树中的最小值
        if (curr.right != null) {
            return min(curr.right);
        }
        // 2、如果该节点没有右子树，则返回最近的从右而来的祖先节点的值
        if (lastAncestorFromRight == null) { // 一直在右走
            return null;
        }
        return lastAncestorFromRight.value;
    }

    /**
     * 根据关键字删除节点
     *
     * @param key 关键字
     * @return 被删除的节点的值
     */
    public V delete(K key) {
        List<V> result = new ArrayList<>();
        root = doDelete1(root, key, result);
        if (result.isEmpty()){
            return null;
        }
        return result.get(0);
        // return doDelete2(key);
    }

    /**
     * 当前树和另外一棵树是否为同一颗
     *
     * @param tree 树
     * @return 一样返回true
     */
    public boolean isSame(BSTTree<K, V> tree) {
        BSTNode<K, V> root1 = this.root;
        BSTNode<K, V> root2 = tree.getRoot();
        return isSame(root1, root2);
    }

    /**
     * less方法，查找所有比key小的节点的value
     *
     * @param key key
     * @return 所有比key小的节点的value构成的集合
     */
    public List<V> less(K key) {
        // List<V> list = new ArrayList<>();
        // doLess1(root, key, list);
        // return list;
        return doLess2(key);
    }

    /**
     * greater方法：查找所有比key都大的节点的value
     *
     * @param key key
     * @return 所有 比key大的节点的value构成的集合
     */
    public List<V> greater(K key) {
        // List<V> result = new ArrayList<>();
        // doGreater1(root,key,result);
        // return result;
        return doGreater2(key);
    }

    /**
     * between方法，求在key1到key2之间的节点的值构成的value
     * @param key1 key1
     * @param key2 key2
     * @return 满足要求的节点的value构成的集合
     */
    public List<V> between(K key1, K key2){
        List<V> result = new ArrayList<>();
        doBetween1(root,key1,key2,result);
        return result;
        // return doBetween2(key1,key2);
    }

    /**
     * toString重写方法
     * @return 重写后的输出时的字符串
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        TreeTraversal.levelOrder(root, a -> builder.append(a.toString()).append(", "));
        builder.append("]");
        return builder.toString();
    }

    /**
     * 判断两颗二叉搜索树是否为同一棵树
     *
     * @param root1 树1的根节点
     * @param root2 树2的根节点
     * @return 为同一颗返回true
     */
    private boolean isSame(BSTNode<K, V> root1, BSTNode<K, V> root2) {
        // 递的时候看当前树的根节点的key和value是否相等
        if (root1 == null && root2 == null) {
            return true;
        } else if (root1 == null || root2 == null) {
            return false;
        } else {
            if (root1.key.compareTo(root2.key) == 0) {
                if (root1.value.equals(root2.value)) {
                    // 如果相等则比较两颗树的左子树是否相等，右子树是否相等
                    return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
                }
                return false;
            }
            return false;
        }
    }

    /**
     * 递归实现less方法
     *
     * @param key key
     */
    private void doLess1(BSTNode<K, V> root, K key, List<V> list) {
        if (root == null) {
            return;
        }
        doLess1(root.left, key, list);
        if (root.key.compareTo(key) < 0) {
            list.add(root.value);
        }
        doLess1(root.right, key, list);
    }

    /**
     * 非递归实现less方法
     *
     * @param key key
     * @return 比key大的所有节点的value构成的集合
     */
    private List<V> doLess2(K key) {
        BSTNode<K, V> curr = root;
        LinkedList<BSTNode<K, V>> stack = new LinkedList<>();
        List<V> result = new ArrayList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                BSTNode<K, V> last = stack.pop();
                if (last.key.compareTo(key) < 0) {
                    result.add(last.value);
                } else {
                    break;
                }
                curr = last.right;
            }
        }
        return result;
    }

    /**
     * 递归方式实现greater方法(反向中序遍历)
     * @param key key
     */
    private void doGreater1(BSTNode<K,V> root, K key, List<V> list){
        if (root == null){
            return;
        }
        doGreater1(root.right,key,list);
        if (key.compareTo(root.key) < 0){
            list.add(root.value);
        }
        doGreater1(root.left,key,list);
    }

    /**
     * 用非递归方式实现greater方法(反向中序遍历)
     * @param key key
     * @return 比key大的所有节点的value集合
     */
    private List<V> doGreater2(K key){
        BSTNode<K, V> curr = root;
        LinkedList<BSTNode<K, V>> stack = new LinkedList<>();
        List<V> result = new ArrayList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.right;
            } else {
                BSTNode<K, V> last = stack.pop();
                if (key.compareTo(last.key) < 0) {
                    result.add(last.value);
                }else {
                    break;
                }
                curr = last.left;
            }
        }
        return result;
    }

    /**
     * 用递归方式实现between方法
     * @param root 当前树
     * @param key1 key1
     * @param key2 key2
     * @param list 存放满足节点大于key1小于key2要求的节点的value
     */
    private void doBetween1(BSTNode<K,V> root, K key1, K key2, List<V> list){
        if (root == null){
            return;
        }
        doBetween1(root.left, key1, key2, list);
        if (key1.compareTo(root.key) <= 0 && root.key.compareTo(key2) <= 0){
            list.add(root.value);
        }
        doBetween1(root.right, key1, key2, list);
    }

    /**
     * 用非递归方式实现between方法
     * @param key1 key1
     * @param key2 key2
     * @return 满足大于key1小于key2的节点的值构成的集合
     */
    private List<V> doBetween2(K key1, K key2){
        BSTNode<K,V> curr = root;
        LinkedList<BSTNode<K, V>> stack = new LinkedList<>();
        List<V> result = new ArrayList<>();
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                curr = curr.left;
            }else {
                BSTNode<K, V> last = stack.pop();
                if (key1.compareTo(last.key) <= 0 && last.key.compareTo(key2) <= 0){
                    result.add(last.value);
                }
                curr = last.right;
            }
        }
        return result;
    }

    /**
     * 用递归的方式实现doGet
     *
     * @param root 树的根节点
     * @param key  关键字
     * @return 查找到的值
     */
    private V doGet1(BSTNode<K, V> root, K key) {
        // 递归结束条件：当前树为空
        if (root == null) {
            return null;
        }
        // key在右子树，则查找右子树的key
        if (root.key.compareTo(key) < 0) {
            return doGet1(root.right, key);
        }
        // key在左子树，则查找左子树的key
        else if (key.compareTo(root.key) < 0) {
            return doGet1(root.left, key);
        }
        // 当前树的根节点就是要查找的
        else {
            return root.value;
        }
    }

    /**
     * 用非递归的方式实现doGet
     *
     * @return 查找到的值
     */
    private V doGet2(K key) {
        // 尾递归可以很太容易的转换成非递归
        BSTNode<K, V> curr = root;
        while (curr != null) {
            if (key.compareTo(curr.key) < 0) {
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                curr = curr.right;
            } else {
                return curr.value;
            }
        }
        return null;
    }

    /**
     * 用递归方式实现doMin
     *
     * @param root 树的根节点
     * @return 最小值
     */
    private V doMin1(BSTNode<K, V> root) {
        // 特殊情况：root为null，会有空指针异常
        if (root == null) {
            return null;
        }
        // 递归结束条件：当前树没有左子树了
        if (root.left == null) {
            return root.value;
        }
        // 递的时候找左子树的最小值
        return doMin1(root.left);
        // 归的时候返回找到的值
    }

    /**
     * 用非递归方式实现doMin
     *
     * @return 最小值
     */
    private V doMin2(BSTNode<K, V> root) {
        if (root == null) {
            return null;
        }
        BSTNode<K, V> curr = root;
        // 如果当前节点没有左子树，则为最小节点
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr.value;
    }

    /**
     * 用递归方式实现doMax
     *
     * @param root 树的根节点
     * @return 最大值
     */
    private V doMax1(BSTNode<K, V> root) {
        if (root == null) {
            return null;
        }
        // 递归结束条件：当前树没有右子树了
        if (root.right == null) {
            return root.value;
        }
        return doMax1(root.right);
    }

    /**
     * 用非递归方式实现doMax
     *
     * @return 最大值
     */
    private V doMax2(BSTNode<K, V> root) {
        if (root == null) {
            return null;
        }
        // 当节点没有右子树时，该节点就是最大值
        BSTNode<K, V> curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        return curr.value;
    }

    /**
     * 用递归方式实现doPut1
     *
     * @param key    待添加二叉搜索树节点的key
     * @param value  待添加二叉树的节点的value
     * @param root   二叉搜索树的根节点
     * @param parent 上一次处理的根节点
     */
    private void doPut1(K key, V value, BSTNode<K, V> root, BSTNode<K, V> parent) {
        // 特殊情况，root为null，会有空指针异常，让新增的节点作为root
        if (root == null && parent == null) {
            this.root = new BSTNode<>(key, value);
            return;
        }
        // 递归退出条件
        if (root == null) {
            if (key.compareTo(parent.key) < 0) {
                // key应该在左边添加
                parent.left = new BSTNode<>(key, value);
                return;
            } else if (parent.key.compareTo(key) < 0) {
                // key应该在右边添加
                parent.right = new BSTNode<>(key, value);
                return;
            } else {
                return; // 这种情况不可能发生，因为parent传进来肯定是null，防止编译器爆黄
            }
        }
        if (key.compareTo(root.key) < 0) {
            // 新增的key value应在当前的左子树中添加或替换
            parent = root;
            doPut1(key, value, root.left, parent);
        } else if (root.key.compareTo(key) < 0) {
            // 新增的key value应在当前的右子树中添加或替换
            parent = root;
            doPut1(key, value, root.right, parent);
        } else {
            // 在当前树中找到key了，就更新value值
            root.value = value;
        }
    }

    /**
     * 用非递归方式实现doPut2
     *
     * @param key   待添加二叉树节点的key
     * @param value 待添加二叉树节点的value
     */
    private void doPut2(K key, V value) {
        // 根节点为null，直接添加就行
        if (root == null) {
            root = new BSTNode<>(key, value);
        }
        BSTNode<K, V> curr = root;
        BSTNode<K, V> parent = null;
        while (curr != null) {
            if (key.compareTo(curr.key) < 0) {
                parent = curr;
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                parent = curr;
                curr = curr.right;
            } else {
                // key在二叉搜索树中本来就存在
                curr.value = value;
                return;
            }
        }
        if (key.compareTo(parent.key) < 0) {
            parent.left = new BSTNode<>(key, value);
        } else { // 只有大于0和小于0两种情况
            parent.right = new BSTNode<>(key, value);
        }
    }

    /**
     * 用递归方式实现delete方法，删除二叉搜索树的指定节点
     * @param root 当前树的头节点
     * @param key 关键字key
     * @param result 用来存放待删除节点的值的集合
     * @return 返回的是当前树删除指定节点重构后形成的新树的头节点
     */
    private BSTNode<K, V> doDelete1(BSTNode<K, V> root, K key, List<V> result) {
        if (root == null){ // 树为空
            return null;
        }
        if (key.compareTo(root.key) < 0){ // 指定删除节点在当前树的根节点的左子树
            root.left = doDelete1(root.left, key, result); // 这里调用返回的是在左子树中删除指定节点后重构而成的新左子树的头节点，让当前树的头节点的left指向新的左子树
        }else if (root.key.compareTo(key) < 0){ // 指定删除节点在当前树的根节点的右子树
            root.right = doDelete1(root.right, key, result); // 这里调用返回的是在左子树中删除指定节点重构而成的新左子树的头节点，让当前树的头节点的right指向新的左子树
        }else {
            // 到了这里说明当前树的头节点就是要删除的节点，则可以将其值存放到result中
            result.add(root.value);
            // 当前树头节点没有左子树或者既没有左子树也没有右子树，重构当前树
            if (root.left == null){
                root = root.right;
                return root;
            }
            // 当前树头节点没有右子树而且必有左子树，重构当前树，加else是因为两个子树都为空的情况下虽然都能行得通，但只能处理一次
            else if (root.right == null){
                root = root.left;
                return root;
            }
            // 当前树头节点既有左子树也有右子树，重构当前树
            else {
                // 因为必有右子树，那么后继节点必定是在右子树中
                BSTNode<K,V> successor = root.right;
                while (successor.left != null){
                    successor = successor.left;
                }
                // 删除右子树中的后继节点，并重构右子树返回右子树的头节点，将删除节点替换为后继节点
                root.right = doDelete1(root.right, successor.key, new ArrayList<>());
                root.key = successor.key; // 用更改值的方式代替修改指针，也就是不要让后继节点直接成为新的root节点
                root.value = successor.value;
                return root;
            }
        }
        return root;
    }

    /**
     * 用非递归方式实现删除操作
     *
     * @param key 待删除节点的key
     * @return 删除节点，如果有返回该节点，没有或者树为空返回null
     */
    private V doDelete2(K key) {
        BSTNode<K, V> curr = root;
        BSTNode<K, V> parent = null;
        while (curr != null) {
            if (key.compareTo(curr.key) < 0) {
                parent = curr;
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                parent = curr;
                curr = curr.right;
            } else {
                break;
            }
        }
        // 如果curr为null，可能root本来就是null，也有可能没找到key
        if (curr == null) {
            return null;
        }
        // 情况一：被删除的节点没有左子树，但有右子树，把右子树接上去就可以，被删除的节点在其父节点的哪边，被顶上去的右子树也应该接到哪边。
        if (curr.left == null) { // 情况三走这条路可以，但是只能走一次
            shift(parent, curr, curr.right);
        }
        // 情况二：被删除的节点没有右子树，但有左子树，把左子树接上去就可以，被删除的节点在其父节点的哪边，被顶上去的左子树也应该接到哪边。
        else if (curr.right == null) { // 情况三走这条路也可以，但是只能走一次
            shift(parent, curr, curr.left);
        }
        // 情况四：被删除的节点有右子树也有左子树
        if (curr.left != null && curr.right != null) {
            // 1、找到被删除节点的后继节点
            BSTNode<K, V> successor = curr.right;
            BSTNode<K, V> sParent = null;
            while (successor.left != null) {
                sParent = successor;
                successor = successor.left;
            }
            // 2、判断删除节点是否与后继节点相邻，（后继节点是否是删除节点的右子树的根节点，如果是，说明删除节点的右子树中没有左子树）
            // 3、如果删除节点与后继节点相邻，则直接把删除节点的右子树顶上来，让右子树的头节点也就是后继节点顶替原来删除节点的位置，再让删除节点的左子树接到后继节点左子树上即可
            // 4、如果删除节点与后继节点不相邻：
            if (curr.right != successor) {
                // 4.1、先把后继节点的后事处理好，也就是把后继节点的右子树（不可能有左子树，右子树要么null要么有）接到后继节点的父节点的左子树上（后继节点肯定是其父节点的左子节点）
                shift(sParent, successor, successor.right); // 后继节点不可能有左子树，将后继节点的右子树托孤给后继节点的父节点
                // 4.2、让后继节点替换删除节点的位置，并让原删除节点的左子树、右子树接到后继节点的左子树、右子树，
                successor.right = curr.right;
            }
            shift(parent, curr, successor); // 将后继节点托孤给删除节点的父节点
            successor.left = curr.left;
        }
        return curr.value;
    }

    /**
     * 托孤方法
     *
     * @param parent  被删除节点的父节点
     * @param deleted 被删除节点
     * @param child   被顶上去的节点，需要托孤给parent的树
     */
    private void shift(BSTNode<K, V> parent, BSTNode<K, V> deleted, BSTNode<K, V> child) {
        if (parent == null) {
            root = child;
        } else if (parent.left == deleted) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }
}
